#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "pila.h"
#include "abb_avl.h"

#define DER 1
#define IZQ -1


/* *********************************************************************
 *			DECLARACION DE LOS TIPOS DE DATO
 * ********************************************************************/

/* Nodos que estructuran el abb */
typedef struct abb_nodo {
	
	char* clave;
	void* valor;
	struct abb_nodo* h_izq;
	struct abb_nodo* h_der;
	size_t altura;

}abb_nodo_t;


/* Arbol binario de busqueda */
struct abb {
	
	abb_nodo_t* raiz;
	abb_comparar_clave_t comparar_clave;
	abb_destruir_dato_t destruir_dato;
	size_t cantidad; /* Invariable de cantidad de nodos */
	
};

/* Iterador externo */
struct abb_iter {
	
	pila_t* pila;
	
};

/* ********************************************************************
 *	************************* FUNCIONES AVL ***************************
 * ********************************************************************/

size_t abb_nodo_altura (abb_nodo_t* nodo){

	if (!nodo)
		return -1;

	return nodo->altura;


}


size_t abb_max_altura_hijos(abb_nodo_t* nodo_actual){

	return abb_nodo_altura(nodo_actual->h_der) > abb_nodo_altura(nodo_actual->h_izq)
				? abb_nodo_altura(nodo_actual->h_der) : abb_nodo_altura(nodo_actual->h_izq);


}


static abb_nodo_t* abb_rotacion_simple_izquierda(abb_nodo_t* nodo){

	abb_nodo_t* nodo_aux = nodo->h_izq;
	nodo->h_izq = nodo_aux->h_der;
	nodo_aux->h_der = nodo;

	nodo->altura = abb_max_altura_hijos(nodo) + 1;
	nodo_aux->altura = abb_max_altura_hijos(nodo_aux) + 1;

	return nodo_aux;

}


static abb_nodo_t* abb_rotacion_simple_derecha(abb_nodo_t* nodo){

	abb_nodo_t* nodo_aux = nodo->h_der;
	nodo->h_der = nodo_aux->h_izq;
	nodo_aux->h_izq = nodo;

	nodo->altura = abb_max_altura_hijos(nodo) + 1;
	nodo_aux->altura = abb_max_altura_hijos(nodo_aux) + 1;

	return nodo_aux;

}


static abb_nodo_t* abb_rotacion_doble_izquierda(abb_nodo_t* nodo){

	nodo->h_izq = abb_rotacion_simple_derecha(nodo->h_izq);

	return abb_rotacion_simple_izquierda(nodo);

}


static abb_nodo_t* abb_rotacion_doble_derecha(abb_nodo_t* nodo){

	nodo->h_der = abb_rotacion_simple_izquierda(nodo->h_der);

	return abb_rotacion_simple_derecha(nodo);

}



/* ********************************************************************
 *	***************** FUNCIONES AUXILIARES ****************************
 * ********************************************************************/

abb_nodo_t* abb_nodo_obtener_min(abb_nodo_t** nodo){

	abb_nodo_t* nodo_actual = *nodo;

	if (!nodo_actual) return NULL;

	if (!nodo_actual->h_izq){

		if (nodo_actual->h_der){
			*nodo = nodo_actual->h_der;
			nodo_actual->h_der->altura = abb_max_altura_hijos(nodo_actual->h_der);
		} else {
			*nodo = NULL;
		}

		return nodo_actual;
	}

	return abb_nodo_obtener_min(&(nodo_actual->h_izq));

}

abb_nodo_t* abb_nodo_obtener_max(abb_nodo_t** nodo){

	abb_nodo_t* nodo_actual = *nodo;

	if (!nodo_actual) return NULL;

	if (!nodo_actual->h_der){

		if (nodo_actual->h_izq){
			*nodo = nodo_actual->h_izq;
			nodo_actual->h_izq->altura = abb_max_altura_hijos(nodo_actual->h_izq);

		} else {
			*nodo = NULL;
		}

		nodo_actual->h_izq = NULL;
		nodo_actual->h_der = NULL;

		return nodo_actual;
	}

	return abb_nodo_obtener_max(&(nodo_actual->h_der));

}

abb_nodo_t* abb_nodo_crear (const char* clave, void* valor){
	
	/* Pido memoria para el nuevo dato */
	abb_nodo_t *nuevo_nodo = malloc (sizeof(abb_nodo_t));
	if (!nuevo_nodo) /* Control de errores */
		return NULL;
	
	/* Pido memoria para la clave y la copio */
	nuevo_nodo->clave = malloc ((strlen(clave)+1)*sizeof(char));
	if (!nuevo_nodo->clave){ /* Control de errores */
		free (nuevo_nodo);
		return NULL;
	}
	strcpy (nuevo_nodo->clave,clave);
	
	/* Asigno el valor */
	nuevo_nodo->valor = valor;
	
	/* Asigno NULL a los hijos */
	nuevo_nodo->h_der = NULL;
	nuevo_nodo->h_izq = NULL;
	nuevo_nodo->altura = 0;
	
	/* Devuelvo el dato */
	return nuevo_nodo;

}

/* Solo el nodo, hay que guardar los hijos para conservarlos*/
void abb_nodo_destruir (abb_avl_t* abb, abb_nodo_t* nodo){
	
	free (nodo->clave);
	if (abb->destruir_dato)
		abb->destruir_dato (nodo->valor);
	
	free (nodo);
	
}

abb_nodo_t* abb_nodo_guardar (abb_avl_t* abb, abb_nodo_t* nodo, abb_nodo_t* nuevo_nodo){
	
	if (!nodo){
		
		return nuevo_nodo;
	}

	/* Caso remplazar clave */
	if (abb->comparar_clave (nodo->clave,nuevo_nodo->clave) == 0){
		nuevo_nodo->h_izq = nodo->h_izq;
		nuevo_nodo->h_der = nodo->h_der;
		abb_nodo_destruir (abb,nodo);
		return nuevo_nodo;
	}


	/* Veo si es menor o mayor a la clave del nodo actual para decidir
	 * de que lado debe estar el nuevo nodo  */
	if (abb->comparar_clave (nuevo_nodo->clave,nodo->clave) < 0){

		nodo->h_izq = abb_nodo_guardar (abb, nodo->h_izq, nuevo_nodo);

		if ( ( abb_nodo_altura ( nodo->h_izq ) - abb_nodo_altura ( nodo->h_der ) ) == 2 ){

			if (abb->comparar_clave (nuevo_nodo->clave,nodo->h_izq->clave) < 0 ){
				nodo = abb_rotacion_simple_izquierda(nodo);
			} else {
				nodo = abb_rotacion_doble_izquierda(nodo);
			}

		}

	} else {

		nodo->h_der = abb_nodo_guardar (abb,nodo->h_der,nuevo_nodo);

		if ( ( abb_nodo_altura ( nodo->h_der ) - abb_nodo_altura (nodo->h_izq ) ) == 2 ){

			if ( abb->comparar_clave (nuevo_nodo->clave,nodo->h_der->clave) > 0 ){
				nodo = abb_rotacion_simple_derecha(nodo);
			} else {
				nodo = abb_rotacion_doble_derecha(nodo);
			}

		}

	}

	nodo->altura = abb_max_altura_hijos(nodo) + 1;


	return nodo;


}

void* abb_nodo_obtener (const abb_avl_t* abb, abb_nodo_t* nodo, const char* clave){
	
	if (!nodo)
		return NULL;
	
	if (abb->comparar_clave (clave,nodo->clave) == 0)
		return nodo;
		
	if (abb->comparar_clave (clave,nodo->clave) < 0)
		return abb_nodo_obtener (abb,nodo->h_izq,clave);
	
	return abb_nodo_obtener (abb,nodo->h_der,clave);
		
	
}

void* abb_nodo_borrar (abb_avl_t* abb, abb_nodo_t** nodo, const char* clave){

	abb_nodo_t* nodo_actual = *nodo;

	if (!nodo_actual)
		return NULL;

	if (abb->comparar_clave(clave,nodo_actual->clave) == 0){

		abb_nodo_t* nueva_raiz = abb_nodo_obtener_max ( &(nodo_actual->h_izq) );

		if (nueva_raiz){
			nueva_raiz->h_der = nodo_actual->h_der;
			nueva_raiz->h_izq = nodo_actual->h_izq;
		} else {

			nueva_raiz = nodo_actual->h_der;

		}

		*nodo = nueva_raiz;

		void* valor = nodo_actual->valor;
		free(nodo_actual->clave);
		free(nodo_actual);

		return valor;

	}

	if (abb->comparar_clave(clave,nodo_actual->clave) < 0)
		return abb_nodo_borrar(abb, &(nodo_actual->h_izq) ,clave);

	return abb_nodo_borrar(abb, &(nodo_actual->h_der),clave);

}

void abb_nodos_destruir (abb_avl_t* abb,abb_nodo_t* nodo){

	if (!nodo)
		return;

	abb_nodos_destruir (abb,nodo->h_izq);
	abb_nodos_destruir (abb,nodo->h_der);

	abb_nodo_destruir (abb,nodo);

}

/* ********************************************************************
 *	***************** IMPLEMENTACION PRIMITIVAS ***********************
 * ********************************************************************/


abb_avl_t* avl_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato){
	
	/* Reservo memoria para el arbol binario */
	abb_avl_t* abb = malloc (sizeof (abb_avl_t));
	if (!abb) /* Control de errores */
		return NULL;
		
	/* Inicializo los campos */
	abb->comparar_clave = cmp;
	abb->destruir_dato = destruir_dato;
	
	abb->raiz = NULL;
	
	abb->cantidad = 0;

	/* Devuelvo el abb creado */
	return abb;

}

bool avl_guardar(abb_avl_t *arbol, const char *clave, void *dato){
	
	bool pertenece = avl_pertenece (arbol,clave);
	
	/* Creo el nodo con la clave y el dato */
	abb_nodo_t* nuevo_nodo = abb_nodo_crear (clave,dato);
	if (!nuevo_nodo)
		return false;
	
	/* Guardo el nuevo nodo, si la clave ya existe, modifica el dato */	
	arbol->raiz = abb_nodo_guardar (arbol,arbol->raiz,nuevo_nodo);

	if (!pertenece)
		arbol->cantidad++;
		
	return true;
		
}

void *avl_borrar(abb_avl_t *arbol, const char *clave){
	
	/* Borro el nodo, pero conservo el valor para devolverlo */
	void* valor = abb_nodo_borrar (arbol,&arbol->raiz,clave);
	if (!valor){
		return NULL;
	}
	
	/* Disminuyo la cantidad de elementos */
	arbol->cantidad--;
	
	/* Devuelvo el valor del nodo que borre */
	return valor;
	
}

void *avl_obtener(const abb_avl_t *arbol, const char *clave){
	
	/* Busco un nodo con la clave dada */
	abb_nodo_t* nodo = abb_nodo_obtener (arbol,arbol->raiz,clave);
	if (!nodo) /* Si no existe el nodo con esa clave devuelvo NULL */
		return NULL;
		
	return nodo->valor;
		
}

bool avl_pertenece(const abb_avl_t *arbol, const char *clave){
	
	/* Busco un nodo con la clave dada */
	abb_nodo_t* nodo = abb_nodo_obtener (arbol,arbol->raiz,clave);
	if (!nodo) /* Si no existe el nodo con esa clave devuelvo false */
		return false;
		
	return true;
	
}

size_t avl_cantidad(abb_avl_t *arbol){
	
	return arbol->cantidad;
	
}

size_t avl_altura(abb_avl_t *arbol){

	return arbol->raiz->altura;

}

void avl_destruir(abb_avl_t *arbol){
	
	if (arbol->raiz) {
		abb_nodos_destruir(arbol,arbol->raiz);
	}
	free (arbol);
	
}



/* *********************************************************************
 * 			IMPLEMENTACION ITERADOR INTERNO
 * ********************************************************************/
void nodo_en_orden(abb_nodo_t *nodo, bool funcion(const char * , void *, void *,void*), void *extra, void* extra2){
	/*si es NULL vuelve*/
	if (!nodo) return;
	/*tratar izquierdo*/
	nodo_en_orden(nodo->h_izq, funcion, extra, extra2);
	/*tratar actual*/
	if (funcion)funcion (nodo->clave,nodo->valor,extra, extra2);
	/*tratar derecho*/
	nodo_en_orden(nodo->h_der, funcion, extra, extra2);
}

 
void avl_in_order(abb_avl_t *arbol, bool funcion(const char * , void *, void *,void*), void *extra, void* extra2){
	/*llama a la funcion anterior*/
	nodo_en_orden(arbol->raiz, funcion, extra, extra2);
	
}


/* *********************************************************************
 * 			IMPLEMETACION ITERADOR EXTERNO
 * ********************************************************************/
 
avl_iter_t *avl_iter_in_crear(const abb_avl_t *arbol){
	
	/*reservo memoria*/
	avl_iter_t* iter = malloc(sizeof(avl_iter_t));
	if (!iter) return NULL;
	
	/*reservo memoria para la pila*/
	iter->pila = pila_crear();
	if (!iter->pila) return NULL;
	
	abb_nodo_t* nodo = arbol->raiz;
	/*si esta vacio devuelvo*/
	if (!nodo) return iter;
	
	/*avanzo hasta el primero(inorder)*/
	while (nodo){
		if (!pila_apilar(iter->pila,nodo)) return NULL;
		nodo = nodo->h_izq;
	}
	
	/*devuelvo*/
	return iter;
}


bool avl_iter_in_avanzar(avl_iter_t *iter){
	
	/*si esta al final no avanza*/
	if (avl_iter_in_al_final(iter)) return false;
	
	/*obtengo el actual*/
	abb_nodo_t* nodo =  pila_desapilar(iter->pila);
	/*si no hay actual vuelve false*/
	if (!nodo) return false;
	/*si tiene hijo derecho, lo apila*/
	if (nodo->h_der) {
		
		nodo = nodo->h_der;
		if (!pila_apilar(iter->pila,nodo)) return false;
		/*y a todos sus hijos izquierdos*/
		nodo = nodo->h_izq;
		while (nodo){
			if (!pila_apilar(iter->pila,nodo)) return false;
			nodo = nodo->h_izq;
		}
	} 
	
	return true;
}


const char *avl_iter_in_ver_actual(const avl_iter_t *iter){
	/*si esta al final devuelve NULL*/
	if (avl_iter_in_al_final(iter)) return NULL;
	/*veo el actual*/
	abb_nodo_t* nodo = pila_ver_tope(iter->pila);
	/*si no hay actual vuelve false*/
	if (!nodo) return NULL;
	/*devuelvo la clave del actual*/
	return nodo->clave;
}


bool avl_iter_in_al_final(const avl_iter_t *iter){
	/*si no hay elementos apilados es que llego al final*/
	return pila_esta_vacia(iter->pila);
}


void avl_iter_in_destruir(avl_iter_t* iter){
	/*destruyo la pila & libero*/
	pila_destruir(iter->pila);
	free(iter);	
}

